package Q144

import java.util.*


class Main {

}

class TreeNode2(var `val`: Int) {
    var left: TreeNode2? = null
    var right: TreeNode2? = null
}

/**
 * 这是递归写法
 */
class SolutionKT1 {
    fun preorderTraversal(root: TreeNode2?): List<Int> {
        val result: MutableList<Int> = ArrayList()
        preorder(root, result)
        return result
    }

    fun preorder(root: TreeNode2?, result: MutableList<Int>) {
        if (root == null) {
            return
        }
        result.add(root.`val`)
        preorder(root.left, result)
        preorder(root.right, result)
    }
}

/**
 * 这里用层序遍历
 */
class SolutionKT{
    fun preorderTraversal(root: TreeNode2?) : List<Int>{
        val res : MutableList<Int> = ArrayList<Int>()
        if(root == null){
            return res
        }
        val stack : Stack<TreeNode2> = Stack()
        stack.push(root)
        while(!stack.isEmpty()){
            var pop = stack.pop()
            res.add(pop.`val`)
            if(pop.right != null){
                stack.push(pop.right!!)
            }
            if(pop.left != null){
                stack.push(pop.left!!)
            }
        }
        return res
    }
}


